package day2;

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Test9 {
    public static void main(String[] args) {
        int[] nums = new int[10001];
        nums[1] = 1;
        nums[2] = 2;
        for(int i = 3; i < 10001; i++) {
            nums[i] = nums[i-1] + nums[i-2];
            nums[i] = nums[i] % 10000;
        }
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < n; i++) {
                int x = in.nextInt();
                sb.append(String.format("%04d",nums[x]));
            }
            System.out.println(sb);
        }
    }
}